package dmsxl.huisu;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * Author: Zhang Dongwei
 * Date: 2023/7/17 20:17
 * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
 * <p>
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * <p>
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 * <p>
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 */
public class hs20_51 {

    static List<List<String>> res = new ArrayList<>();

    public static void main(String[] args) {
        res = solveNQueens(4);
        System.out.println(res);
    }

    public static List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        backTrack(n, 0, chessboard);
        return res;
    }

    public static void backTrack(int n, int row, char[][] chessboard) {
        if (row == n) {
            res.add(Array2List(chessboard));
            return;
        }
        for (int col = 0;col < n; col++) {
            if (isValid (row, col, n, chessboard)) {
                chessboard[row][col] = 'Q';
                backTrack(n, row+1, chessboard);
                chessboard[row][col] = '.';
            }
        }
    }

    public static boolean isValid(int row, int col, int n, char[][] chessboard) {
        // 检查列
        for (int i=0; i<row; i++) { // 相当于剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }
        // 检查45度对角线
        for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        // 检查135度对角线
        for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    public static List Array2List(char[][] chessboard) {
        List<String> list = new ArrayList<>();
        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }
}

// 方法2：使用boolean数组表示已经占用的直(斜)线
//class Solution {
//    List<List<String>> res = new ArrayList<>();
//    boolean[] usedCol, usedDiag45, usedDiag135;    // boolean数组中的每个元素代表一条直(斜)线
//    public List<List<String>> solveNQueens(int n) {
//        usedCol = new boolean[n];                  // 列方向的直线条数为 n
//        usedDiag45 = new boolean[2 * n - 1];       // 45°方向的斜线条数为 2 * n - 1
//        usedDiag135 = new boolean[2 * n - 1];      // 135°方向的斜线条数为 2 * n - 1
//        //用于收集结果, 元素的index表示棋盘的row，元素的value代表棋盘的column
//        int[] board = new int[n];
//        backTracking(board, n, 0);
//        return res;
//    }
//    private void backTracking(int[] board, int n, int row) {
//        if (row == n) {
//            //收集结果
//            List<String> temp = new ArrayList<>();
//            for (int i : board) {
//                char[] str = new char[n];
//                Arrays.fill(str, '.');
//                str[i] = 'Q';
//                temp.add(new String(str));
//            }
//            res.add(temp);
//            return;
//        }
//
//        for (int col = 0; col < n; col++) {
//            if (usedCol[col] | usedDiag45[row + col] | usedDiag135[row - col + n - 1]) {
//                continue;
//            }
//            board[row] = col;
//            // 标记该列出现过
//            usedCol[col] = true;
//            // 同一45°斜线上元素的row + col为定值, 且各不相同
//            usedDiag45[row + col] = true;
//            // 同一135°斜线上元素row - col为定值, 且各不相同
//            // row - col 值有正有负, 加 n - 1 是为了对齐零点
//            usedDiag135[row - col + n - 1] = true;
//            // 递归
//            backTracking(board, n, row + 1);
//            usedCol[col] = false;
//            usedDiag45[row + col] = false;
//            usedDiag135[row - col + n - 1] = false;
//        }
//    }
//}